package Hot_100;

import org.junit.Test;

public class T64_minPathSum {
    @Test
    public void test() {
        int[][]mg= {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
//        minPathSum_1(mg);
        System.out.println(minPathSum_2(mg));
    }

    public int minPathSum_2(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int memo[][] = new int[m][n];
        return DFS(m, n, 0, 0, memo, grid);
    }

    int DFS(int m, int n, int x, int y,int memo[][],int [][]grid) {
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return Integer.MAX_VALUE;
        }

        if (x == m - 1 && y == n - 1) {
            return grid[x][y];
        }

        if (memo[x][y] != 0) {
            return memo[x][y];
        }

        int v1 = DFS(m, n, x + 1, y, memo, grid);
        int v2 = DFS(m, n, x, y + 1, memo, grid);

        int min = Math.min(v1, v2) + grid[x][y];
        memo[x][y] = min;
        return min;
    }


//    ------------------------dp-------------------------------------
    public int minPathSum_1(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}
